home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / a_utils / _archvrs / unix / unzip51 / unreduce.c < prev    next >
C/C++ Source or Header  |  1992-11-04  |  6KB  |  217 lines
  1. /*---------------------------------------------------------------------------
  2.  
  3.   unreduce.c
  4.  
  5.   The Reducing algorithm is actually a combination of two distinct algorithms.
  6.   The first algorithm compresses repeated byte sequences, and the second al-
  7.   gorithm takes the compressed stream from the first algorithm and applies a
  8.   probabilistic compression method.
  9.  
  10.   ---------------------------------------------------------------------------*/
  11.  
  12.  
  13. #include "unzip.h"
  14.  
  15.  
  16. /**************************************/
  17. /*  UnReduce Defines, Typedefs, etc.  */
  18. /**************************************/
  19.  
  20. #define DLE    144
  21.  
  22. typedef uch f_array[64];        /* for followers[256][64] */
  23.  
  24. static void LoadFollowers __((void));
  25. void flush OF((unsigned));      /* routine from inflate.c */
  26.  
  27.  
  28.  
  29. /*******************************/
  30. /*  UnReduce Global Variables  */
  31. /*******************************/
  32.  
  33. #if defined(MACOS) || defined(MTS) || defined(MALLOC_WORK)
  34.    f_array *followers;     /* shared work space */
  35. #else
  36.    f_array *followers = (f_array *) (slide + 0x4000);
  37. #endif
  38.  
  39. uch Slen[256];
  40. int factor;
  41.  
  42. int L_table[] =
  43. {0, 0x7f, 0x3f, 0x1f, 0x0f};
  44.  
  45. int D_shift[] =
  46. {0, 0x07, 0x06, 0x05, 0x04};
  47. int D_mask[] =
  48. {0, 0x01, 0x03, 0x07, 0x0f};
  49.  
  50. int B_table[] =
  51. {8, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5,
  52.  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6,
  53.  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  54.  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7,
  55.  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  56.  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  57.  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  58.  7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  59.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  60.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  61.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  62.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  63.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  64.  8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  65.  8, 8, 8, 8};
  66.  
  67.  
  68.  
  69.  
  70.  
  71. /*************************/
  72. /*  Function unReduce()  */
  73. /*************************/
  74.  
  75. void unReduce()   /* expand probabilistically reduced data */
  76. {
  77.     register int lchar = 0;
  78.     int nchar;
  79.     int ExState = 0;
  80.     int V = 0;
  81.     int Len = 0;
  82.     longint s = ucsize;  /* number of bytes left to decompress */
  83.     unsigned w = 0;      /* position in output window slide[] */
  84.     unsigned u = 1;      /* true if slide[] unflushed */
  85.  
  86.  
  87. #if defined(MACOS) || defined(MTS) || defined(MALLOC_WORK)
  88.     followers = (f_array *) (slide + 0x4000);
  89. #endif
  90.  
  91.     factor = lrec.compression_method - 1;
  92.     LoadFollowers();
  93.  
  94.     while (s > 0 /* && (!zipeof) */) {
  95.         if (Slen[lchar] == 0)
  96.             READBIT(8, nchar)   /* ; */
  97.         else {
  98.             READBIT(1, nchar);
  99.             if (nchar != 0)
  100.                 READBIT(8, nchar)       /* ; */
  101.             else {
  102.                 int follower;
  103.                 int bitsneeded = B_table[Slen[lchar]];
  104.                 READBIT(bitsneeded, follower);
  105.                 nchar = followers[lchar][follower];
  106.             }
  107.         }
  108.         /* expand the resulting byte */
  109.         switch (ExState) {
  110.  
  111.         case 0:
  112.             if (nchar != DLE) {
  113.                 s--;
  114.                 slide[w++] = (uch)nchar;
  115.                 if (w == 0x4000) {
  116.                     flush(w);
  117.                     w = u = 0;
  118.                 }
  119.             }
  120.             else
  121.                 ExState = 1;
  122.             break;
  123.  
  124.         case 1:
  125.             if (nchar != 0) {
  126.                 V = nchar;
  127.                 Len = V & L_table[factor];
  128.                 if (Len == L_table[factor])
  129.                     ExState = 2;
  130.                 else
  131.                     ExState = 3;
  132.             } else {
  133.                 s--;
  134.                 slide[w++] = DLE;
  135.                 if (w == 0x4000)
  136.                 {
  137.                   flush(w);
  138.                   w = u = 0;
  139.                 }
  140.                 ExState = 0;
  141.             }
  142.             break;
  143.  
  144.         case 2:{
  145.                 Len += nchar;
  146.                 ExState = 3;
  147.             }
  148.             break;
  149.  
  150.         case 3:{
  151.                 register unsigned e;
  152.                 register unsigned n = Len + 3;
  153.                 register unsigned d = w - ((((V >> D_shift[factor]) &
  154.                                D_mask[factor]) << 8) + nchar + 1);
  155.  
  156.                 s -= n;
  157.                 do {
  158.                   n -= (e = (e = 0x4000 - ((d &= 0x3fff) > w ? d : w)) > n ?
  159.                         n : e);
  160.                   if (u && w <= d)
  161.                   {
  162.                     memset(slide + w, 0, e);
  163.                     w += e;
  164.                     d += e;
  165.                   }
  166.                   else
  167.                     if (w - d < e)      /* (assume unsigned comparison) */
  168.                       do {              /* slow to avoid memcpy() overlap */
  169.                         slide[w++] = slide[d++];
  170.                       } while (--e);
  171.                     else
  172.                     {
  173.                       memcpy(slide + w, slide + d, e);
  174.                       w += e;
  175.                       d += e;
  176.                     }
  177.                   if (w == 0x4000)
  178.                   {
  179.                     flush(w);
  180.                     w = u = 0;
  181.                   }
  182.                 } while (n);
  183.  
  184.                 ExState = 0;
  185.             }
  186.             break;
  187.         }
  188.  
  189.         /* store character for next iteration */
  190.         lchar = nchar;
  191.     }
  192.  
  193.     /* flush out slide */
  194.     flush(w);
  195. }
  196.  
  197.  
  198.  
  199.  
  200.  
  201. /******************************/
  202. /*  Function LoadFollowers()  */
  203. /******************************/
  204.  
  205. static void LoadFollowers()
  206. {
  207.     register int x;
  208.     register int i;
  209.  
  210.     for (x = 255; x >= 0; x--) {
  211.         READBIT(6, Slen[x]);
  212.         for (i = 0; (uch)i < Slen[x]; i++) {
  213.             READBIT(8, followers[x][i]);
  214.         }
  215.     }
  216. }
  217.